Overlay networks are used for communication between data compute nodes that belong to the same logical network. To implement the overlays, tunnels are created to transport packets between hypervisors. A method to detect the health state of the tunnels is typically used to ensure that the overlay network is operating properly. One method creates individual sessions for each hypervisor pair in which communications may happen. Then, heartbeat messages are introduced between all of the pairs to check tunnel health. In a network, there may be a large amount of possible hypervisor pairs and the introduction of the heartbeat messages for all the pairs introduces significant network traffic into the network.